package test.heightcheck;

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        int[] heights={1,1,4,2,1,3};
        System.out.println(new Solution().heightChecker(heights));
    }
    public int heightChecker(int[] heights) {
//        输入：heights = [1,1,4,2,1,3]
//        输出：3
//        解释：
//        当前数组：[1,1,4,2,1,3]
//        目标数组：[1,1,1,2,3,4]
//        1 <= heights.length <= 100
//        1 <= heights[i] <= 100
        int[] arr = new int[101];
        for (int height : heights) {
            arr[height]++;
        }
        int count = 0;
        for (int i = 1, j = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                if (heights[j++] != i) count++;
            }
        }
        return count;
        /*int length = heights.length;
        int[] target = new int[length];
        System.arraycopy(heights, 0, target, 0, length);
        Arrays.sort(target);
        int result = 0;
        for (int i = 0; i < length; i++) {
            if (heights[i] != target[i]) {
                result++;
            }
        }
        return result;*/
    }
}
